package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q1281 {
    /**
     * @param nums: the given array
     * @param k: the given k
     * @return: the k most frequent elements
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        // write your code here
    	List<Integer> rs = new ArrayList<>();
    	if(nums == null) {
    		return rs;
    	}
    	Map<Integer, Integer> map = new HashMap<>();
    	for(int num : nums) {
    		Integer i = map.get(num);
    		if(i == null) {
    			i = 0;
    		}
    		i ++;
    		map.put(num, i);
    	}
    	List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
    	Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {

			@Override
			public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
				if(!o1.getValue().equals(o2.getValue())) {
					return o2.getValue() - o1.getValue();
				}else {
					return o1.getKey().compareTo(o2.getKey());
				}
			}
		});
    	for(int i = 0; i< k; i++) {
    		rs.add(list.get(i).getKey());
    	}
    	return rs;
    }


}
